|
In the theory of formal languages, Ogden's lemma (named after William F. Ogden) provides an extension of flexibility over the pumping lemma for context-free languages. Ogden's lemma states that if a language ''L'' is context-free, then there exists some number ''p'' > 0 (where ''p'' may or may not be a pumping length) such that for any string ''w'' of length at least ''p'' in ''L'' and every way of "marking" ''p'' or more of the positions in ''w'', ''w'' can be written as :''w'' = ''uxyzv'' with strings ''u'', ''x'', ''y'', ''z'', and ''v'', such that #''xz'' has at least one marked position, #''xyz'' has at most ''p'' marked positions, and #''uxiyziv'' is in ''L'' for every ''i'' ≥ 0. Ogden's lemma can be used to show that certain languages are not context-free, in cases where the pumping lemma for context-free languages is not sufficient. An example is the language . It is also useful to prove the inherent ambiguity of some languages. Observe that when every position is marked, this lemma is equivalent to the pumping lemma for context-free languages. == See also == * Pumping lemma for context-free languages * Pumping lemma for regular languages 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ogden's lemma」の詳細全文を読む スポンサード リンク
|